package com.liufei.class05;

import java.util.HashSet;

public class Code01_BitMap1 {


    // 这里不对。错误原因是 1 << (num & 63) 的1应该是 1L
    public static class BitMap {
        private long[] bits;

        public BitMap(int max) {
            // 0 ~ 63 需要一个
            // (max + 64) >> 6 => (max + 64) / 64
            bits = new long[(max + 64) >> 6];
        }


        public void add(int num) {
            // 先确定在数组中索引的位置 bit[num >> 6] => bit[num / 64]
            // 在确定在64位中是哪个位置  num & 63 => num / 64
            // 1L << (num & 63)，1左移这么多位，假设是k，那k这个位置上就是1，然后需要将1替换上去。
            // 我们知道，两个数 a | b，只有都是0的时候才是0，只要有一个1就是1，所以这里使用 ｜(或)
            bits[num >> 6] |= (1 << (num & 63));
        }

        public void delete(int num) {
            // 删除就是将其设置位0，需要使用 & ，& 表示只有 1 和 1，才是1，其它都是0
            // 1L << (num & 63)，1左移这么多位，假设是k，那k这个位置上就是1，然后取反，那么k位置就是0，使用&，不管之前位置是0还是1，结果都是0
            bits[num >> 6] &= ~(1 << (num & 63));
        }

        public boolean contains(int num) {
            // 检查 k 位置上是0还是1，1表示存在
            // 1L << (num & 63)，1左移这么多位，假设是k，那k这个位置上就是1，使用 &，只有具体位置上的是1，结果才是1
            return (bits[num >> 6] & (1 << (num & 63))) != 0;
        }
    }


    public static void main(String[] args) {
        System.out.println("测试bitMap开始");
        int testTime = 1000000;
        int max = 432432;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTime; i++) {
            int num = (int)(Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.33) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.66) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                boolean b1 = bitMap.contains(num);
                boolean b2 = set.contains(num);
                if (b1 != b2) {
                    System.out.println(num);
                    System.out.println("Oops!");
                    break;
                }
            }
        }
        for (int i = 0; i <= max ; i++) {
            if (bitMap.contains(i) != set.contains(i)) {
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
